package com.gofaraway.service.student.leetcode;

import java.io.UnsupportedEncodingException;
import java.util.*;
import java.util.stream.Collectors;

/**
 * @author ChenPeng
 * @Date 2024/6/8 10:21
 */
public class Demo01 {

    /**
     * 字母异位词分组
     * 示例 1:
     * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
     * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
     * <p>
     * 题解思路：
     * 创建一个 map
     * key存放 排好序后的字符串  value存放 异位词集合
     * 关键点：排序
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            //排序
            Arrays.sort(array);
            String key = new String(array);
            //通过key获取value 没有就默认创建一个list
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }


    /**
     * 字母异位词分组
     * 示例 1:
     * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
     * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
     * <p>
     * 题解思路：
     * 创建一个 map
     * key存放 排好序后的字符串  value存放 异位词集合
     * 关键点：排序
     */
    public static List<List<String>> groupAnagramsV2(String[] strs) {

        HashMap<String, List<String>> hashMap = new HashMap<>();

        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            List<String> strings = hashMap.getOrDefault(Arrays.toString(charArray), new ArrayList<>());

            strings.add(str);
            hashMap.put(Arrays.toString(charArray), strings);
        }
        return new ArrayList<>(hashMap.values());
    }

    public static void main(String[] args) {
//        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
//        groupAnagrams(strs);

        int[] nums = {1, 1, 0, 0, 12, 0, 15, 8, 7, 0, 0};
        moveZeroes(nums);
    }


    /**
     * 移动零：
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     * <p>
     * 双指针解法
     *
     * @param nums
     */
    public static void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        groupAnagrams(strs);

        List<List<String>> lists = groupAnagramsV2(strs);
        for (List<String> list : lists) {
            System.out.println(list);
        }
    }


    /**
     * 移动零：
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     * <p>
     * 解法思路：
     * 不为 0 的元素填充在数组前面，遍历完所有不为 0 的数后，剩下的索引为全部赋值为0。done
     */
    public void moveZeroesV2(int[] nums) {
        int s = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[s++] = nums[i];
            }
        }

        for (int i = s; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

}
